package top;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 *
 *  打乱数组
 *
 * @author chenyw
 * @date 2022/7/22 15:47
 */
public class Top384Solution {
//    int[] arr;
//    List<Integer> list;
//    Random random;
//    public Top384Solution(int[] nums) {
//        random = new Random();
//        list = new ArrayList<>();
//        arr = new int[nums.length];
//        for (int i = 0; i < nums.length; i++) {
//            arr[i] = nums[i];
//            list.add(nums[i]);
//        }
//    }
//
//    public int[] reset() {
//        return arr;
//    }
//
//    public int[] shuffle() {
//        int[] tmp = new int[arr.length];
//        for (int i = 0; i < arr.length; i++) {
//            int j = random.nextInt(list.size());
//            tmp[i] = list.get(j);
//            int last = list.get(list.size() - 1);
//            list.set(j, last);
//            //删除非末尾元素需要O(n)的时间复杂度
//            list.remove(list.size() - 1);
//        }
//        for (int i = 0; i < arr.length; i++) {
//            list.add(arr[i]);
//        }
//        return tmp;
//    }


    //O(n)时间复杂度
    int[] nums;
    int[] original;
    public Top384Solution(int[] nums) {
        this.nums = nums;
        original = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            original[i] = nums[i];
        }
    }

    public int[] reset() {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = original[i];
        }
        return nums;
    }

    public int[] shuffle() {
        Random random = new Random();
        for (int i = 0; i < nums.length; i++) {
            int j = i + random.nextInt(nums.length - i);
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }

}
